Machine translation (MT) concerns the automatic translation of natural language sentences from a first language (e.g., French) into another language (e.g., English). Systems that perform MT techniques are said to “decode” the source language into the target language.
One type of MT decoder is the statistical MT decoder. A statistical MT decoder that translates French sentences into English may include a language model (LM) that assigns a probability P(e) to any English string, a translation model (TM) that assigns a probability P(f|e) to any pair of English and French strings, and a decoder. The decoder may take a previously unseen sentence f and try to find the e that maximizes P(e|f), or equivalently maximizes P(e)·P(f|e).
A “stack decoder” is a type of statistical MT decoder. In a stack decoder, possible translations are organized into a graph structure and then searched until an optimal solution (translation) is found. Although stack decoders tend to produce good results, they do so at a significant cost. Maintaining and searching a large potential solution space is expensive, both computationally and in terms of computer memory.